/*
 * VertexSet.cpp
 *
 *  Created on: Jan 24, 2014
 *      Author: ik
 */

using namespace std;

#include <VertexSet.h>

inline static Lista &_lista(NODETYPE copia, Lista & l, int offset)
{
	int e = LEAST(copia);
	while( e >= 0 )
	{
		l += (e + offset);
		copia &= ~(ONE << e);
		e = LEAST(copia);
	}

	return l;
}

inline static Lista &_lista(NODETYPE bitset, const int from, const int to, Lista & l, int offset)
{
	return _lista(bitset & ((ALLONE << from) & (ALLONE >> (BSIZE-to))), l, offset);
}

SingleNodeSetIterator SingleNodeSetIterator::SingleNodeSetEnd;

Lista &SingleNodeSet::lista(const int from, const int to, Lista & l, int offset) const
{
	return _lista(*_bitset, from, to, l, offset);
}

Lista &SingleNodeSet::lista(Lista & l, int offset) const {
	return _lista(*_bitset, l, offset);
}

Lista &SingleNodeSet::lista(Lista & l) const {
	return _lista(*_bitset, l, 0);
}

Lista &SingleNodeSet::listaDiferenca(const BitMapSet &otro, Lista & l) const
{
	return _lista(*_bitset & ~(*((SingleNodeSet &) otro)._bitset), l, 0);
}

void SingleNodeSet::print() const
{
	int e;
	NODETYPE c = *_bitset;
	cout << "[ ";
	while ((e = LEAST(c)) >= 0) {
		cout << " " << e;
		c &= ~(ONE << e);
	}
	cout << " ]" << endl;
}

VertexSetIterator VertexSetIterator::VertexSetEnd;

VertexSet::VertexSet(const VertexSet &c) : _n(c._n), _nw(c._nw)
{
	_bitset = new NODETYPE[_nw];
	memcpy(_bitset, c._bitset, _nw << LOGBYTE);
}

/*!
 * \brief Creates an empty new VertexSet
 */
VertexSet::VertexSet(int n) : _n(n), _nw(n >> LOGB)
{
	if ((_nw << LOGB) != _n)
		_nw++;
	_bitset = new NODETYPE[_nw];
	memset(_bitset, 0, _nw << LOGBYTE);
}

int VertexSet::least() const
{
	int i = 0;
	while (i < _nw && _bitset[i] == 0)
		i++;

	return i < _nw ? NELEM(i)+LEAST(_bitset[i]) : -1;
}

bool VertexSet::isSubsetOf(const BitMapSet &otro) const
{
	int i = 0;
	while (i < _nw && (_bitset[i] == (_bitset[i] & ((VertexSet &) otro)._bitset[i])))
		i++;

	return (i == _nw);
}

bool VertexSet::isDisjoint(const BitMapSet &otro) const
{
	return !intersects(otro);
}

bool VertexSet::intersects(const BitMapSet &otro) const
{
	int i = 0;
	while (i < _nw && ((_bitset[i] & ((VertexSet &) otro)._bitset[i]) == 0))
		i++;

	return (i < _nw);
}

bool VertexSet::intersects(const BitMapSet &otro1, const BitMapSet &otro2) const
{
	int i = 0;
	while (i < _nw && ((_bitset[i] & ((VertexSet &) otro1)._bitset[i] & ((VertexSet &) otro2)._bitset[i]) == 0))
		i++;

	return (i < _nw);
}

bool VertexSet::containsInter(const BitMapSet &otro1, const BitMapSet &otro2) const
{
	int i = 0;
	bool ret = true;
	while (i < _nw && ret) {
		NODETYPE inter = ((VertexSet &) otro1)._bitset[i] & ((VertexSet &) otro2)._bitset[i];
		ret = (_bitset[i] && inter) == inter;
		i++;
	}

	return ret;
}

bool VertexSet::isEqual(const BitMapSet &otro) const
{
	int i = 0;
	while (i < _nw && (_bitset[i] == ((VertexSet &) otro)._bitset[i]))
		i++;

	return (i == _nw);
}

Lista& VertexSet::lista(const int from, const int to, Lista & l) const
{
	int node = NODEIDX(from);
	int last = NODEIDX(to-1);
	int offset = NELEM(node);

	if (node == last)
	{
		_lista(_bitset[node], IDXINNODE(from), IDXINNODE(to), l, offset);

		return l;
	}

	_lista(_bitset[node++], IDXINNODE(from), BSIZE, l, offset);
	offset += BSIZE;

	while (node < last)
	{
		_lista(_bitset[node++], l, offset);
		offset += BSIZE;
	}

	return _lista(_bitset[node], 0, IDXINNODE(to), l, offset);
}

Lista& VertexSet::listaDiferenca(const BitMapSet &otro, Lista & l) const
{
	int node = 0;
	int last = _nw-1;
	int offset = NELEM(node);

	while (node < last)
	{
		_lista(_bitset[node] & ~(((VertexSet &) otro)._bitset[node]), l, offset);
		node++;
		offset += BSIZE;
	}

	return _lista(_bitset[node] & ~(((VertexSet &) otro)._bitset[node]), l, offset);
}

void VertexSet::print() const
{
	int e;
	cout << "[";
	for(int i = 0; i < _nw; i++)
	{
		NODETYPE c = _bitset[i];
		while ((e = LEAST(c)) >= 0) {
			c &= ~(ONE << e);
			e += NELEM(i);
			cout << " " << e;
		}
	}
	cout << " ]" << endl;
}

int VertexSet::size() const
{
	int size = 0;
	for (int i = 0; i < _nw; i++)
		size += POPCOUNT(_bitset[i]);
	return size;
}

bool VertexSet::isEmpty() const
{
	int i = 0;
	while (i < _nw && _bitset[i] == 0)
		i++;
	return i == _nw;
}

/*!
 * If \c otro does not implement VertexSet, then an error occurs.
 */
void VertexSet::addAll(const BitMapSet &otro)
{
	for (int i = 0; i < _nw; i++)
		_bitset[i] |= ((VertexSet &) otro)._bitset[i];
}

void VertexSet::addAll(const int from, const int to)
{
	int fromidx = IDXINNODE(from);
	int toidx = IDXINNODE(to);
	int fromnode = NODEIDX(from);
	int tonode = NODEIDX(to);

	if (fromnode == tonode)
	{
		_bitset[fromnode] |= ((ALLONE << from) & (ALLONE >> (BSIZE-toidx)));
		return;
	}

	if (fromidx > 0)
		_bitset[fromnode] |= (ALLONE << fromidx);
	if (toidx > 0)
		_bitset[fromnode] |= (ALLONE >> (BSIZE-toidx));
	memset(_bitset+fromnode, 0xFF, (tonode-fromnode+1) << LOGBYTE);
}

/*!
 * If \c otro does not implement VertexSet, then an error occurs.
 */
void VertexSet::retainAll(const BitMapSet &otro)
{
	for (int i = 0; i < _nw; i++)
		_bitset[i] &= ((VertexSet &) otro)._bitset[i];
}

/*!
 * If \c otro does not implement VertexSet, then an error occurs.
 */
void VertexSet::removeAll(const BitMapSet &otro)
{
	for (int i = 0; i < _nw; i++)
		_bitset[i] &= ~((VertexSet &) otro)._bitset[i];
}

/*!
 * If \c otro does not implement VertexSet, then an error occurs.
 */
void VertexSet::symmetDiff(const BitMapSet &otro)
{
	for (int i = 0; i < _nw; i++)
		_bitset[i] ^= ((VertexSet &) otro)._bitset[i];
}

void VertexSet::turnToCompl()
{
	for (int i = 0; i < _nw-1; i++)
		_bitset[i] = ~_bitset[i];
	_bitset[_nw-1] ^= (ALLONE >> (BSIZE - IDXINNODE(_n)));
}

void VertexSet::copyCompl(const BitMapSet &otro)
{
	for (int i = 0; i < _nw-1; i++)
		_bitset[i] = ~((VertexSet &) otro)._bitset[i];
	_bitset[_nw-1] = ((VertexSet &) otro)._bitset[_nw-1] ^ (ALLONE >> (BSIZE - IDXINNODE(_n)));
}

VertexSet * VertexSet::newUnmodifiable() {
	return new UnmodifiableVertexSet(*this);
}

VertexSet * VertexSet::turnToUnmodifiable() {
	VertexSet * ret = new UnmodifiableVertexSet(_n, _nw, _bitset, size());
	_n = 0;
	_nw = 0;
	_bitset = NULL;
	return ret;
}
